function Point(x, y, name) {
    this.name = name;
    this.lat = x;
    this.lng = y;
}

Point.prototype.setPosition = function(x, y) {
  this.lat = x;
  this.lng = y;
};

Point.prototype.setGroup = function(group) {
  this.group = group;
};

Point.prototype.clone = function() {
    return (new Point(this.x, this.y, this.name));
};

function KMeansClustering() {}

var R = 100, ER = 6371 * 1000;

var dataSet = null, centroids = null;

function calDist(point1, point2) {
    var lat1 = point1.lat,
        lat2 = point2.lat,
        lon1 = point1.lng,
        lon2 = point2.lng;
    var dLat = (lat2 - lat1) * Math.PI / 180,  // deg2rad below
        dLon = (lon2 - lon1) * Math.PI / 180;
    var a = 0.5 - Math.cos(dLat)/2 + Math.cos(lat1 * Math.PI / 180) * Math.cos(lat2 * Math.PI / 180) * (1 - Math.cos(dLon))/2;

    return ER * 2 * Math.asin(Math.sqrt(a));
}

function compareGroup(group1, group2) {
    if (group1.length != group2.length) {
        return false;
    } else {
        for (var i = group1.length - 1; i >= 0; i--) {
            if (group1[i].length !== group2[i].length) {
                return false;
            } else {
                for (var j = group1[i].length; j >= 0; j--) {
                    if (group1[i][j] !== group2[i][j]) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

function copyGroup(group) {
    var newGroup = [];
    for (var i = 0, j = group.length; i < j; i ++) {
        newGroup.push(group[i]);
    }
    return newGroup;
}

function calGroupCentroid (group) {
    for (var i = group.length - 1; i >= 0; i --) {
        var x = 0, y = 0;
        var curGroup = group[i], gLen = curGroup.length;
        if (gLen > 0) {
            for (var j = gLen - 1; j >= 0; j --) {
                x += dataSet[curGroup[j]].lat;
                y += dataSet[curGroup[j]].lng;
            }
            x = x / gLen;
            y = y / gLen;
            centroids[i].setPosition(x, y);
        }
    }
}

KMeansClustering.prototype.clustering = function (data) {
    dataSet = data;
    centroids = [new Point(dataSet[0].lat, dataSet[0].lng, "g_0")];
    
    var curGroup = [],
        preGroup = [];   
    while(true) {
        curGroup = [];
        for (var i = centroids.length - 1; i >=0 ; i --) {
            curGroup.push([]);    
        }
        for (var pi = dataSet.length - 1; pi >= 0; pi --) {
            var minIndex = -1, minDist = -1;
            for (var gi = 0; gi < centroids.length; gi ++) {
                var distance = calDist(dataSet[pi], centroids[gi]);                
                if (distance < minDist || minDist == -1) {
                    minDist = distance;
                    minIndex = gi;
                }
            }
            if (minDist < R) {
                curGroup[minIndex].push(pi);
            } else {
                curGroup.push([pi]);
                centroids.push(new Point(dataSet[pi].lat, dataSet[pi].lng, "g_"+centroids.length));
            }
        }
        if (compareGroup(curGroup, preGroup)) {            
            break;
        } else {
            preGroup = copyGroup(curGroup);
            calGroupCentroid(curGroup);
        }
    }
    
    return {centroids: centroids, groups: curGroup};
};